package algorithm.monotonousStack;

import java.util.Stack;

public class LargestRectangleHistogram {

    public static int largestRectangleArea(int[] height){
        Stack<Integer> stack = new Stack<>();
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < height.length; i++) {
            while(!stack.isEmpty() && height[stack.peek()] >= height[i]){
                Integer pop = stack.pop();
                int start = stack.isEmpty()? -1 : stack.peek();
                int end = i - 1;
                max = Math.max((end - start) * height[pop], max);
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            Integer pop = stack.pop();
            int start = stack.isEmpty()? -1 : stack.peek();
            int end = height.length - 1;
            max = Math.max((end - start) * height[pop], max);
        }
        return max;
    }

    public static int largestRectangleArea2(int[] height){
        int[] stack = new int[height.length];
        int last = -1;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < height.length; i++) {
            while(last != -1 && height[stack[last]] >= height[i]){
                Integer pop = stack[last--];
                int start = last == -1? -1 : stack[last];
                int end = i - 1;
                max = Math.max((end - start) * height[pop], max);
            }
            stack[++last] = i;
        }
        while(last != -1){
            Integer pop = stack[last--];
            int start = last == -1? -1 : stack[last];
            int end = height.length - 1;
            max = Math.max((end - start) * height[pop], max);
        }
        return max;
    }

    public static void main(String[] args) {

        int[] height = {2,4};
        System.out.println(largestRectangleArea2(height));
    }
}
